#include <stdlib.h>
#include <stdio.h>

// 迪杰斯特拉算法(Dijkstra)，求最短路径

typedef char VertexType; // 顶点数据类型
typedef int EdgeType;  // 边的权值类型
#define MAXVEX 100       // 最大顶点数
#define MAXEDGES 200     // 最大边数
#define MAX 0x10000   // 无穷大

typedef struct{
    int begin;      // 边的起点
    int end;        // 边的终点
    int weight;     // 边的权值
} Edge;

typedef struct{
    Edge edges[MAXEDGES]; // 边集数组
    int numEdges;          // 当前边数
} EdgeList;

// 图的邻接矩阵表示
typedef struct{
    VertexType vexs[MAXVEX];          // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];     // 邻接矩阵
    int numVertexes, numEdges;        // 图的当前顶点数和边数
} Graph;


void createGraph(Graph *G){
    G->numVertexes = 9;
    G->numEdges = 16;
    // 初始化邻接矩阵
    G->vexs[0] = 'A';
    G->vexs[1] = 'B';
    G->vexs[2] = 'C';
    G->vexs[3] = 'D';
    G->vexs[4] = 'E';
    G->vexs[5] = 'F';
    G->vexs[6] = 'G';
    G->vexs[7] = 'H';
    G->vexs[8] = 'I';

    for (int i = 0; i < G->numVertexes; i++){      // 初始化邻接矩阵
        for (int j = 0; j < G->numVertexes; j++){  // 初始化邻接矩阵
            if (i == j){                  
                G->arc[i][j] = 0;  // 对角线为0
            } else {
                G->arc[i][j] = MAX; // 用无穷大表示不连通
            }
        }
    }

    // 建立边(权值)
    //  
    G->arc[0][1] = 1;
    G->arc[0][2] = 5;

    G->arc[1][2] = 3;  
    G->arc[1][3] = 7;
    G->arc[1][4] = 5;

    G->arc[2][3] = 1;
    G->arc[2][4] = 7;

    G->arc[3][4] = 2;
    G->arc[3][6] = 3;

    G->arc[4][5] = 3;
    G->arc[4][6] = 6;
    G->arc[4][7] = 9;

    G->arc[5][7] = 5;

    G->arc[6][7] = 2;
    G->arc[6][8] = 7;

    G->arc[7][8] = 4;

    for (int i = 0; i < G->numVertexes; i++){
        for (int j = 0; j < G->numVertexes; j++){
            G->arc[j][i] = G->arc[i][j]; // 无向图邻接矩阵对称
        }
    }
}

// 选择未访问的顶点中距离最小的顶点
int choose(int dist[], int found[], int numVertexes){
    int min = MAX;
    int k = -1;
    for (int i = 0; i < numVertexes; i++){
        if (found[i] == 0 && dist[i] < min){ // 找到未走过的顶点中距离最小的
            min = dist[i];
            k = i;
        }
    }
    return k; // 返回该顶点下标
}

// dijkstra算法
void dijkstra(Graph G, int begin){
    int found[MAXVEX]; // 顶点是否走过
    int path [MAXVEX];  // 最短路径数组
    int dist [MAXVEX];  // 顶点间的距离
    for (int i = 0; i < G.numVertexes; i++){
        found[i] = 0; // 初始化都没走过
        path[i] = -1; // 初始化路径数组
        dist[i] = G.arc[begin][i]; // 初始化距离数组
    }
    found[begin] = 1; // 标记起点走过
    dist[begin] = 0; // 起点到起点距离为0

    int next = 0; // 下一个顶点下标
    for (int i = 1; i<G.numVertexes; i++){ // 遍历所有顶点
         next = choose(dist, found, G.numVertexes); // 选择下一个顶点
         found[next] = 1; // 标记该顶点走过
         for (int j = 0; j < G.numVertexes; j++){ // 更新距离数组和路径数组
             if (found[j] == 0 && (dist[next] + G.arc[next][j] < dist[j])){
                 dist[j] = dist[next] + G.arc[next][j]; // 更新距离
                 path[j] = next; // 更新路径
             }
         }
    }
    // 输出结果
    for (int i = 0; i < G.numVertexes; i++){
        if (i != begin){
            printf("(%c, %c) %d ", G.vexs[begin], G.vexs[i], dist[i]);
            int temp = path[i];
            printf("路径：%c", G.vexs[i]);
            while (temp != -1){
                printf("<-%c", G.vexs[temp]);
                temp = path[temp];
            }
            printf("\n");
        }
    }
}

int main(){
    Graph G;
    createGraph(&G);
    dijkstra(G, 0); // 从顶点0开始
    return 0;
}

